package error

import (
	"fmt"
	. "whoops/leetcode/common"
)

//打家劫舍的基础上换成了二叉树 偷了根节点，则左右节点不能偷，偷了左右节点则根节点不能偷
func rob(root *TreeNode) int {
	dp := make([]int, 2)
	dp[0] = root.Val
	if root.Left != nil && root.Right != nil {
		dp[1] = max(root.Val, root.Left.Val+root.Right.Val)
	} else if root.Left != nil && root.Right == nil {
		dp[1] = max(root.Val, root.Left.Val)
	} else if root.Left == nil && root.Right != nil {
		dp[1] = max(root.Val, root.Right.Val)
	}
	fmt.Println(dp)
	height := 0
	queue := Queue{}
	queue.poll(root)
	for len(queue.Nums) > 0 {
		dp = append(dp, 0)
		height++
		queueLen := len(queue.Nums)
		childrenResult, parentResult := 0, 0
		for queueLen > 0 {
			pop := queue.pop()
			parentResult += pop.Val
			if pop.Left != nil {
				childrenResult += pop.Left.Val
				queue.poll(pop.Left)
			}
			if pop.Right != nil {
				childrenResult += pop.Right.Val
				queue.poll(pop.Right)
			}
			queueLen--
		}
		fmt.Println("children", childrenResult)
		if height >= 2 {
			dp[height] = max(dp[height-1], dp[height-2]+childrenResult)
		}
	}
	fmt.Println("dp", dp)

	return dp[height-1]
}

type Queue struct {
	Nums []*TreeNode
}

func (q *Queue) poll(node *TreeNode) {
	if len(q.Nums) == 0 {
		q.Nums = make([]*TreeNode, 0)
	}
	q.Nums = append(q.Nums, node)
}

func (q *Queue) pop() *TreeNode {
	node := q.Nums[0]
	q.Nums = q.Nums[1:]
	return node
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
